package niuke;

/**
 * description:
 * author:zt
 * date:2021-08-02
 */

import java.util.ArrayList;

/**
 * 合并\ k k 个已排序的链表并将其作为一个已排序的链表返回。分析并描述其复杂度。
 */
public class NC51 {
    public ListNode mergeKLists(ArrayList<ListNode> lists) {
        ListNode res = null;
        for (ListNode list : lists) {
            res = merge(res,list);
        }
        return res;
    }
    public ListNode merge(ListNode p1,ListNode p2){
        if (p1==null || p2==null) return p1==null? p2:p1;

        ListNode head = new ListNode(-1);
        ListNode cur = head;
        while (p1!=null && p2!=null){
            if (p1.val<p2.val) {
                cur.next = p1;
                p1 = p1.next;
            } else {
                cur.next = p2;
                p2 = p2.next;
            }
            cur = cur.next;
        }
        if (p1!=null) cur.next = p1;
        if (p2!=null) cur.next = p2;
        return head.next;
    }
}
